package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释:子数组 [2,3] 有最大乘积 6。
 *
 * @author caijinnan
 */
public class 乘积最大子数组 {

    @Test
    public void run() {
        int[] nums = {2, -5, -2, -4, 3};
        System.out.println(maxProduct(nums));
    }

    public int maxProduct(int[] nums) {
        int dp;
        if (nums.length == 1) return nums[0];
        int i, maxm, minm;
        dp = maxm = minm = nums[0];
        for (i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxm = Math.max(maxm * nums[i], nums[i]);
                minm = Math.min(minm * nums[i], nums[i]);
            } else {
                int tmp = maxm;
                maxm = Math.max(minm * nums[i], nums[i]);
                minm = Math.min(tmp * nums[i], nums[i]);
            }
            dp = Math.max(maxm, dp);
        }
        return dp;
    }
}
